#leetcode题目91：解码方法
#难度：中等

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [1] + [0] * n
        for i in range(1, n + 1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if i > 1 and s[i-2] != '0' and int(s[i-2:i]) <= 26:
                dp[i] += dp[i-2]
        return dp[n]


#测试数据
s = "12"
#预期输出：2 (可以解码为 "AB" (1 2) 或者 "L" (12))
solution = Solution()
print(solution.numDecodings(s))

s = "226"
#预期输出：3 (可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6))
solution = Solution()
print(solution.numDecodings(s))

s = "06"
#预期输出：0 (无法解码，因为 "06" 不能映射为 "F")
solution = Solution()
print(solution.numDecodings(s))